Field of the Invention
The present invention generally relates to a computer system, a method, a program, and a code generation unit for executing multithreaded parallel processing. More particularly the present invention relates to allocating the use of exclusive locks to process critical sections of a task.
Description of the Related Art
In computer systems, multi-threaded systems in which multiple threads perform processing in parallel are known. In a multi-threaded system, when each thread accesses, for example, a shared variable, the thread synchronizes with the other threads. A general synchronization method in multi-threading includes using an exclusive lock to control access.
When a thread acquires an exclusive lock, an atomic instruction such as compare-and-swap needs to be executed. The execution cost of an atomic instruction is higher than those of the other types of instructions. Thus, when an exclusive lock is acquired, the cost of overall processing increases.
Moreover, when an exclusive lock is acquired and released, writing on a lock variable occurs. Thus, when an exclusive lock is frequently acquired and released, cache coherent traffic increases.
A method called sequential lock is known as a method for solving such problems (“Seqlock”, online, WIKIPEDIA, searched Dec. 2, 2009, http://en.wikipedia.org/wiki/Seqlock). A sequential lock is a type of reader/writer lock, and a lock variable is implemented as a counter. When the counter indicates an odd number, this shows that the lock has been acquired. When the counter indicates an even number, this shows that the lock has been released. Every time the lock is acquired and released, the counter is incremented by one.
In a system in which a sequential lock is used, when a thread performs processing in a critical section involving writing, the thread acquires the lock. When a thread performs processing in a critical section not involving writing, the thread performs the following processing.
At the beginning of the critical section, the thread first reads the counter value (lock variable). Subsequently, the thread performs the processing in the critical section. Subsequently, at the end of the critical section, the thread reads the counter value and compares the counter value with that read at the beginning of the critical section. When the values are the same, the thread completes the processing in the critical section. When the values are different, the thread repeats the processing in the critical section from the beginning.
In this manner, in a system in which a sequential lock is used, when processing in a critical section not involving writing is performed, no atomic instruction is executed, and thus the execution cost can be reduced. Moreover, in a system in which a sequential lock is used, since the number of write operations on a lock variable can be reduced, cache coherent traffic can be reduced.
In a known system in which a sequential lock is used, one thread has been incapable of continuously acquiring the same exclusive lock. Thus, in a known system in which a sequential lock is used, in general, performance of processing in a nested critical section, i.e., processing in another critical section inside one critical section, has been prohibited.
Moreover, in a known system in which a sequential lock is used, while processing in a critical section not involving writing is being performed, when processing in another critical section involving writing is performed, the processing in the critical section not involving writing fails. Thus, when processing in a critical section involving writing is frequently performed, processing in a critical section not involving writing and being performed in parallel is not completed for a long time.
Moreover, in a known system in which a sequential lock is used, while a loop process included in a critical section not involving writing is being performed, a thread that is performing processing in another critical section involving writing may rewrite a variable related to a condition for terminating the loop process. In such a case, the loop process included in the critical section not involving writing is not completed.
Moreover, in a known system in which a sequential lock is used, a critical section not involving writing may contain a pointer for specifying a reference from which data is read. In this case, while the processing in the critical section not involving writing is being performed, when another thread writes NULL to the reference of the pointer, the critical section not involving writing accesses NULL and thus stops performance of the processing.
Moreover, in a known system in which a sequential lock is used, a critical section may include a write instruction that is seldom executed. For example, a write instruction included in an IF statement may be seldom executed. However, in a known system in which a sequential lock is used, even in the case of such a critical section including only a write instruction that is seldom executed, the processing needs to be performed by acquiring an exclusive lock.